package com.shuo.dsa.niuke;

import java.util.Stack;

/**
 * <a href="http://www.cnblogs.com/shunyu/p/8592887.html">图解思路</a>
 * <p>
 * 思路: 如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，我们就要把压栈序列中还没有入栈的数字压入辅助栈，
 * 直到把下一个需要弹出的数字压入栈顶为止；如果所有的数字都压入了栈中仍然没有找到下一个弹出的数字，那么该序列就不可能是一个合法的弹出序列
 */
public class IsPopOrder {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;
        for (int aPushA : pushA) {
            stack.push(aPushA);
            while (!stack.empty() && stack.peek() == popA[popIndex]) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.empty();
    }
}
